'''  很难懂，必须记住代码
给你一个字符串 s，找到 s 中最长的回文子串。
回文：左 --> 右 与 左 <-- 右 输出的字符串是一样的

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
'''

# 找出两个相同字符间最长的字符串
# class Solution:
#     def longestPalindrome(self, s:str) -> str:
#         '''
#         这个只能用在回文很短的情况，
#         假如一个回文很长，就失效了 比如'bacbcab'
#         '''
#         s_set = {} # 用于判断是否已经出现过这个字符
#         max_len = 0
#         temp = ""
#         res = ""
#
#         for j in range(len(s)):
#             if s[j] not in s_set:
#                 s_set[s[j]] = j       # 记录第一次出现位置
#             else:
#                 start001 = s_set[s[j]]  # 第一次出现的位置
#                 # end001 = j
#                 if j - s_set[s[j]] > max_len:
#                     max_len = j - s_set[s[j]]
#                     temp = s[start001: j+1]
#                     if temp == temp[::-1]: # 回文字符串正反相同
#                         res = temp # 如果是回文就赋值
#                     else: #若不是回文就改变最初的重复字符位置
#                         s_set[s[j]] = j
#         return res


class Solution(object):
    def longestPalindrome(self, s: str) -> str:
        """
        这种方法更像是滑窗，
        每找到一个回文，就用当前回文长度+2的窗口向左右各多增长1，
        这样可以往前推出更长的回文，
        然后由于用更大的窗口继续向右滑窗，又因为只有找到回文才赋值给res，
        所以不用怕后面突然出现更长的回文。

        好处：不需要对长度进行判断，随着 i 的迭代，最后获得的一定是最长的回文
        """
        res = ''
        for i in range(len(s)):
            # print('len(s): ', len(s))
            print('i: ', i, end='\t')
            # print(i-len(res)-1)
            '''
            i-len(res)-1 的操作很精妙,在发现后面有更长的回文时，它能让起点回到更前面.
            
            每找到一个回文，那么len(res)+2，那么下一个循环，start就会多减2，
            但由于 i++，所以实际上start只会比上一次多左移一个位置，
            
            然后还有一个就是temp = s[start : i+1]中的i+1,
            这个可以让temp在向左扩充判断范围之后，再进一步往右移一位，
            使得可以同时往左往右多判断一位.        
            '''
            start = max(0, i-len(res)-1) # max还可以防止越界
            # print('i-len(res)-1: ', i-len(res)-1, '\t', end='\t')
            # print('len(res): ', len(res), end='\t')
            # print('start: ', start, end='\t')
            temp = s[start : i+1]
            # print('temp: ', temp, end='\t')
            # 分两种情况 奇数和偶数
            if temp == temp[::-1]: # 回文字符串正反相同 # 单字符也是回文
                res = temp
                print('Y: ', res)
            else: # 去掉首字符再判断是否为回文 # 为的是应付前一轮是偶数回文但这一次是奇数个字符
                temp = temp[1:]
                # print(temp)
                if temp == temp[::-1]:
                    res = temp
                print('N: ', res)
        return res



str1 = "caacbabacaacaaabaaacaaabaaa"
s = Solution()
print(s.longestPalindrome(str1))



